prime = []  # 素数列表
phi = []  # 欧拉函数


def pre(n: int, prime=prime, phi=phi):
    phi += [0 for i in range(n + 1)]
    phi[1] = 1
    for i in range(2, n + 1):
        if phi[i] == 0:
            prime.append(i)
            phi[i] = i - 1
        for p in prime:
            if i * p > n:
                break
            if i % p:
                phi[i * p] = phi[i] * phi[p]
            else:
                phi[i * p] = phi[i] * p
                break


if __name__ == "__main__":
    pre(20)
    print(phi)
    print(prime)
